package com.leetcode.partition9;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/11/10 10:17
 */
public class LC847访问所有节点的最短路径dp {

    private static final int N = 13, INF = 0x3f3f3f3f;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        int[][] graph = new int[n][];
        for (int i = 0; i < n; i++) {
            String[] s = reader.readLine().split("\\s+");
            int[] g = new int[s.length];
            for (int j = 0; j < s.length; j++) g[j] = Integer.parseInt(s[j]);
            graph[i] = g;
        }
        writer.write(shortestPathLength(graph));
        writer.flush();
    }

    private static void floyd(int[][] matrix) {
        int n = matrix.length;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
                }
            }
        }
    }

    public static int shortestPathLength(int[][] graph) {
        int n = graph.length;
        //根据邻接表构建邻接矩阵，便于后续找点和floyd的预处理
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = i == j ? 0 : INF;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                matrix[i][graph[i][j]] = 1;
            }
        }
        //弗洛伊德预处理，得到任意两个点之间的距离，避免在进行状态转义的时候，两个不能直达的点数据出现错误
        floyd(matrix);
        //dp[i][j]表示在当前状态i下到达j结点的最小路径
        int[][] dp = new int[1 << n][n];
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], INF);
        //初始化所有起点，起点开始到达自己的最短距离是0
        for (int i = 0; i < n; i++) dp[1 << i][i] = 0;
        //第一种状压dp写法
        for (int status = 1; status < 1 << n; status++) {
            //枚举已经访问过的点
            for (int i = 0; i < n; i++) {
                if ((status >> i & 1) == 0) continue;
                //枚举还未被访问过的点
                for (int j = 0; j < n; j++) {
                    if ((status >> j & 1) == 1) continue;
                    //尝试从i点走到j点
                    dp[status | (1 << j)][j] = Math.min(dp[status | (1 << j)][j], dp[status][i] + matrix[i][j]);
                }
            }
        }
        //第二种状压dp的写法
//        for (int status = 1; status < 1 << n; status++) {
//            //枚举已经访问过的点v和u，在u的状态中，最优状态是v还没有被访问过，也就是dp[status ^ (1 << v)][u]
//            for (int v = 0; v < n; v++) {
//                if ((status >> v & 1) == 0) continue;
//                for (int u = 0; u < n; u++) {
//                    if ((status >> u & 1) == 0) continue;
//                    dp[status][v] = Math.min(dp[status][v], dp[status ^ (1 << v)][u] + matrix[u][v]);
//                }
//            }
//        }
        return Arrays.stream(dp[(1 << n) - 1]).min().getAsInt();
    }
}
